package com.zhugang.week13.stack;


import java.util.Stack;

/**
 * @program algorithms
 * @description: calculate2
 * @author: chanzhugang
 * @create: 2022/11/08 00:48
 */
public class Calculate2 {

    /**
     * 面试题16.26 计算器
     * https://leetcode.cn/problems/calculator-lcci/
     *
     * @param s
     * @return
     */
    public int calculate(String s) {
        /**
         * 思路：数字栈、运算符栈
         * 遍历字符，如果是数字压入数字栈、如果是运算符且优先级高于栈顶运算符压入运算符栈，
         * 否则取出两个数字栈元素和一个运算符栈顶元素计算，结果压入数字栈
         */
        Stack<Integer> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();
        int i = 0;
        int n = s.length();
        while (i < n) {
            char c = s.charAt(i);
            if (c == ' ') {
                i++;
            } else if (isDigit(c)) {
                // 数字， 多个连续数字
                int num = 0;
                while (i < n && isDigit(s.charAt(i))) {
                    // 转成十进制
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                nums.push(num);
            } else {
                // 字符
                if (ops.isEmpty() || prior(c, ops.peek())) {
                    ops.push(c);
                } else {
                    while (!ops.isEmpty() && !prior(c, ops.peek())) {
                        // 计算, 把一些数据消掉，类似连连消
                        fetchAndCal(nums, ops);
                    }
                    // 符号入栈
                    ops.push(c);
                }
                i++;
            }
        }
        while (!ops.isEmpty()) {
            // 还有运算符
            fetchAndCal(nums, ops);
        }
        return nums.pop();
    }

    private void fetchAndCal(Stack<Integer> nums, Stack<Character> ops) {
        Character ospTop = ops.pop();
        Integer num2 = nums.pop();
        Integer num1 = nums.pop();
        int result = cal(num1, num2, ospTop);
        nums.push(result);
    }

    private int cal(Integer num1, Integer num2, Character ops) {
        return switch (ops) {
            case '+' -> num1 + num2;
            case '-' -> num1 - num2;
            case '*' -> num1 * num2;
            default -> num1 / num2;
        };
    }

    private boolean prior(char a, Character b) {
        if ((a == '*' || a == '/') && (b == '+' || b == '-')) {
            return true;
        }
        return false;
    }

    private boolean isDigit(char c) {
        return c >= '0' && c <= '9';
    }

    public static void main(String[] args) {
        Calculate2 calculate2 = new Calculate2();
        String s = "3+2*4";
        int num = calculate2.calculate(s);
        System.out.println(num);
    }
}